/*
 * @Author: szx
 * @Date: 2021-12-12 19:52:23
 * @LastEditTime: 2022-04-14 13:41:31
 * @Description:
 * @FilePath: \leetcode\300-399\347\347.js
 */
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
    const map = new Map();
    for (let i of nums) {
        map.set(i, (map.get(i) || 0) + 1);
    }
    if (map.size < k) return [...map.keys()];
    const heap = [];
    let i = 0;
    map.forEach((value, key) => {
        if (i < k) {
            // 取前k个建堆, 插入堆
            heap.offer(key);
            // 原地建立前 k 堆
            if (i === k - 1) buildHeap(heap, map, k);
        } else if (map.get(heap[1]) < value) {
            // 替换并堆化
            heap[1] = key;
            // 自上而下式堆化第一个元素
            heapify(heap, map, k, 1);
        }
        i++;
    });
    // 删除heap中第一个元素
    heap.shift();
    return heap;
};

// 原地建堆，从后往前，自上而下式建小顶堆
let buildHeap = (heap, map, k) => {
    if (k === 1) return;
    // 从最后一个非叶子节点开始，自上而下式堆化
    for (let i = Math.floor(k / 2); i >= 1; i--) {
        heapify(heap, map, k, i);
    }
};

// 堆化
let heapify = (heap, map, k, i) => {
    // 自上而下式堆化
    while (true) {
        let minIndex = i;
        if (2 * i <= k && map.get(heap[2 * i]) < map.get(heap[i])) {
            minIndex = 2 * i;
        }
        if (2 * i + 1 <= k && map.get(heap[2 * i + 1]) < map.get(heap[minIndex])) {
            minIndex = 2 * i + 1;
        }
        if (minIndex !== i) {
            swap(heap, i, minIndex);
            i = minIndex;
        } else {
            break;
        }
    }
};

// 交换
let swap = (arr, i, j) => {
    [arr[i], arr[j]] = [arr[j], arr[i]];
};
